package demolist;

public class Test {
    public static void main(String[] args) {
        MySingleList mySingleList1 = new demolist.MySingleList();
        mySingleList1.addLast(12);
        mySingleList1.addLast(22);
        mySingleList1.addLast(32);
        mySingleList1.addLast(42);
        mySingleList1.addLast(56);
        mySingleList1.addLast(77);

        mySingleList1.createLoop();

        boolean flg = MySingleList.hasCycle(mySingleList1.head);

        System.out.println(flg);

        MySingleList.ListNode ret = mySingleList1.detecCycle(mySingleList1.head);
        System.out.println(ret.val);
    }


    /**
     * 求两条相交链表的第一个交点（两条链表相交呈y型）
     * @param headA
     * @param headB
     * @return
     */
    public static MySingleList.ListNode getIntersectionNode(MySingleList.ListNode headA, MySingleList.ListNode headB) {
        //1.求两个链表的长度，假设A链表最长
        MySingleList.ListNode pl = headA;
        MySingleList.ListNode ps = headB;
        int lenA = 0;
        int lenB = 0;
        while (pl != null) {
            lenA++;
            pl = pl.next;
        }
        while (ps != null) {
            lenB++;
            ps = ps.next;
        }
        //2.根据链表的长度，决定pl、ps分别指向哪个链表
        pl = headA;
        ps = headB;
        int len = lenA - lenB;
        if (len < 0) {
            pl = headB;
            ps = headA;
            len = lenB - lenA;
        }
        //3.pl走len步，len = Math.abs(lenA - lenB)
        while (len != 0) {
            pl = pl.next;
            len--;
        }
        //4.pl ps一起走，直到相遇
        while (pl != ps) {
            pl = pl.next;
            ps = ps.next;
        }
        if (pl == null) {//当两条链表没有交点时
            return null;
        }
        return pl;
    }


    /**
     * 使两个链表相交
     * @param headA
     * @param headB
     */
    public static void ListIntersection(MySingleList.ListNode headA, MySingleList.ListNode headB) {
        headB.next.next.next = headA.next.next;
    }

    public static void main4(String[] args) {
        MySingleList mySingleList1 = new demolist.MySingleList();
        mySingleList1.addLast(12);
        mySingleList1.addLast(22);
        mySingleList1.addLast(32);//节点
        mySingleList1.addLast(42);
        mySingleList1.addLast(56);
        mySingleList1.addLast(77);

        MySingleList mySingleList2 = new demolist.MySingleList();
        mySingleList2.addLast(18);
        mySingleList2.addLast(36);
        mySingleList2.addLast(40);
        mySingleList2.addLast(55);//无
        mySingleList2.addLast(99);

        ListIntersection(mySingleList1.head, mySingleList2.head);

        mySingleList1.show();
        mySingleList2.show();

        MySingleList.ListNode ret = getIntersectionNode(mySingleList1.head, mySingleList2.head);
        System.out.println(ret.val);
    }



    /**
     * 合并两个升序链表为新的升序链表
     * @param headA
     * @param headB
     * @return
     */
    public static MySingleList.ListNode mergeTwoLists(
            MySingleList.ListNode headA, MySingleList.ListNode headB) {

        MySingleList.ListNode newH = new MySingleList.ListNode(-1);
        MySingleList.ListNode tmpH = newH;
        while (headA != null && headB != null) {
            if (headA.val < headB.val) {
                tmpH.next = headA;
                tmpH = tmpH.next;
                headA = headA.next;
            } else {
                tmpH.next = headB;
                tmpH = tmpH.next;
                headB = headB.next;
            }
        }
        if (headA != null) {
            tmpH.next = headA;
        }
        if (headB != null) {
            tmpH.next = headB;
        }
        return newH.next;
    }

    public static void main3(String[] args) {
        MySingleList mySingleList1 = new demolist.MySingleList();
        mySingleList1.addLast(12);
        mySingleList1.addLast(22);
        mySingleList1.addLast(32);
        mySingleList1.addLast(42);
        mySingleList1.addLast(56);
        mySingleList1.addLast(77);
        mySingleList1.show();

        MySingleList mySingleList2 = new demolist.MySingleList();
        mySingleList2.addLast(18);
        mySingleList2.addLast(36);
        mySingleList2.addLast(40);
        mySingleList2.addLast(55);
        mySingleList2.show();

        MySingleList.ListNode newList = mergeTwoLists(mySingleList1.head, mySingleList2.head);
        mySingleList2.show(newList);
    }



    public static void main2(String[] args) {
        demolist.MySingleList mySingleList = new demolist.MySingleList();
        mySingleList.addLast(1);
        mySingleList.addLast(2);
        mySingleList.addLast(3);
        mySingleList.addLast(4);
        //mySingleList.addLast(5);
        mySingleList.show();

        System.out.println(mySingleList.kthToLast2(1));

        //MySingleList.ListNode ret = mySingleList.reverseList();

//        MySingleList.ListNode ret = mySingleList.findMiddleNode1();
//        System.out.println(ret.val);

//        MySingleList.ListNode ret = mySingleList.findMiddleNode2();
//        System.out.println(ret.val);
    }



    public static void main1(String[] args) {
        demolist.MySingleList mySingleList = new demolist.MySingleList();
//        mySingleList.createList();
//        mySingleList.show();
//        System.out.println();
//        mySingleList.show();
//        System.out.println();
//        System.out.println(mySingleList.size());
//        System.out.println(mySingleList.contains(99));

        mySingleList.addFirst(77);
        mySingleList.addFirst(88);
        mySingleList.addFirst(88);
        mySingleList.addFirst(88);
        mySingleList.show();
        System.out.println();
        System.out.println("======================");

        //mySingleList.addIndex(3, 12);

        //mySingleList.remove(88);

        //mySingleList.removeAllKey(88);

        mySingleList.clear();
        mySingleList.show();
    }
}
